package 中等.链表;

import util.ListNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 给你一个链表的头节点 head，请你编写代码，反复删去链表
 * 中由 总和 值为 0 的连续节点组成的序列，直到不存在这样的序列为止。
 * 删除完毕后，请你返回最终结果链表的头节点。
 * 你可以返回任何满足题目要求的答案。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/remove-zero-sum-consecutive-nodes-from-linked-list
 */
public class 从链表中删去总和值为零的连续节点_1171 {

    public static void main(String[] args) {

        ListNode node0 = new ListNode(0);
        ListNode node1 = new ListNode(1);
        node1.next = node0;

        removeZeroSumSublists(node1);
        System.out.println(node1);

    }

    /**
     * 哈希表+前缀和
     */
    public static ListNode removeZeroSumSublists(ListNode head) {
        // 虚拟头节点，用来删除实际头结点
        ListNode tempNode = new ListNode(0);
        tempNode.next = head;
        boolean hasRemove = true;
        while (hasRemove && tempNode.next != null) {
            hasRemove = false;
            Map<Integer, ListNode> map = new HashMap<>();
            map.put(0, tempNode);

            int preSum = 0;
            ListNode curNode = tempNode.next;
            while (curNode != null) {
                preSum += curNode.val;

                if (map.containsKey(preSum)) {
                    ListNode preNode = map.get(preSum);
                    preNode.next = curNode.next;
                    hasRemove = true;
                    break;
                }

                map.put(preSum, curNode);
                curNode = curNode.next;
            }
        }
        return tempNode.next;
    }

}
